#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;

namespace MySort
{
    template <class T>
    class sort
    {
    public:
        // 插入
        void InsertSort(T &v)
        {
            int n = v.size();

            for (int i = 0; i < n - 1; i++)
            {
                int end = i;
                int tmp = v[end + 1]; // 防止越界，起始的end+1 == n-1位置
                while (end >= 0)
                {
                    if (v[end] > tmp) // 小于前面的数据
                    {
                        v[end + 1] = v[end]; // 前面的数据往后挪
                        end--;
                    }
                    else
                    {
                        // 找到合适的位置，跳出循环
                        break;
                    }
                }
                v[end + 1] = tmp;
            }
        }

        // 希尔
        void ShellSort(vector<int> &v)
        {
            int n = v.size();

            int gap = n;

            // while (gap > 0)
            while (gap > 1)
            {
                // gap /= 2;
                gap = gap / 3 + 1; // 优化

                for (int i = 0; i < n - gap; i++) // 排序的趟数
                {
                    int end = i;
                    int tmp = v[end + gap];
                    while (end >= 0)
                    {
                        if (v[end] > tmp)
                        {
                            v[end + gap] = v[end];
                            end -= gap;
                        }
                        else
                        {
                            break;
                        }
                    }
                    v[end + gap] = tmp;
                }
            }
        }

        // 选择排序
        void SelectSort(T &v)
        {
            int n = v.size();

            for (int i = 0; i < n; i++)
            {
                int min = i;
                for (int j = n - 1; j > i; j--) // 从右边开始往左找最小值下标
                {
                    if (v[j] < v[min])
                    {
                        min = j;
                    }
                }

                // 找到后，放到最小值对应的位置
                swap(v[min], v[i]);
            }
        }

        // 堆排序
        void HeapSort(T &v)
        {
            int n = v.size();

            for (int i = (n - 1) / 2; i >= 0; i--)
            {
                // 建堆
                AdjustDwon(v, n, i);
            }

            // 堆排序
            int end = n - 1;
            while (end >= 0) // 最后一个数据不在堆上即是排序完成
            {
                swap(v[0], v[end]);
                // 向下调整，变成新的大根堆
                AdjustDwon(v, end, 0);
                end--;
            }
        }

        // 冒泡
        void BubbleSort(T &v)
        {
            int n = v.size();

            for (int i = 0; i < n; i++)
            {
                int judge = 0; // 优化处理

                for (int j = 1; j <= (n - 1) - i; j++) // 每次排完都会固定一个数
                {
                    if (v[j - 1] > v[j])
                    {
                        swap(v[j - 1], v[j]);
                        judge = 1;
                    }
                }

                if (judge == 0)
                    break; // 没有进行数据交换，表示原本数据就是有序的直接退出
            }
        }

        // 快排
        void QuickSock(T &v)
        {
            int n = v.size();
            // _QuickSort1(v, 0, n - 1); //递归
            _QuickSort2(v, 0, n - 1); // 非递归
        }

        // 归并
        void MergeSort(T &v)
        {
            int n = v.size();
            T temp(n);

            _MergeSort(v, temp, 0, n - 1);
        }

    private:
        // 快排递归
        void _QuickSort1(T &v, int left, int right)
        {
            if (left >= right)
                return;

            // 递归到一定程度时，使用插入排序来辅助快排：
            // 快排的递归犹如前序遍历，一颗二叉树的最后三层占总节点的87.5%
            // 对此，可以在递归到倒数第4层时，直接用插入排序
            // 15的确定：
            // 1.满二叉树的高度为10，总节点为1023
            // 2.这个二叉树的第6层节点数为：2^6-1=63
            // 3.1023/63 == 15，到倒数第四层就可以使用插入排序
            if ((right - left) + 1 < 15)
            {
                InsertSort(v);
            }
            else
            {
                int mid = _quickSort1(v, left, right); // 确定好一个元素位置
                // int mid = _quickSort2(v, left, right); // 确定好一个元素位置
                // int mid = _quickSort3(v, left, right); // 确定好一个元素位置

                _QuickSort1(v, left, mid - 1);
                _QuickSort1(v, mid + 1, right);
            }
        }

        // 快排非递归：利用栈
        void _QuickSort2(T &v, int left, int right)
        {
            int beign = left, end = right;

            stack<int> sk;
            sk.push(beign);
            sk.push(end);

            while (!sk.empty())
            {
                end = sk.top();
                sk.pop();
                beign = sk.top();
                sk.pop();

                // 排序处理
                // int key = _quickSort1(v, beign, end); //bug
                int key = _quickSort2(v, beign, end);
                // int key = _quickSort3(v, beign, end);


                // 入栈规则：当区间只有一个数据时不再入栈
                if (end > key + 1)
                {
                    sk.push(key + 1);
                    sk.push(end);
                }

                if (beign < key - 1)
                {
                    sk.push(beign);
                    sk.push(key - 1);
                }
            }
        }

        // 快排优化：三数取中
        int GetMidIndex(const T &v, int left, int right)
        {
            int mid = right - ((right - left) >> 1);

            if (v[left] > v[mid])
            {
                if (v[right] < v[mid])
                {
                    return mid;
                }
                else if (v[right] > v[left])
                {
                    return left;
                }
                else
                {
                    return right;
                }
            }
            else if (v[right] > v[mid])
            {
                if (v[left] < v[mid])
                {
                    return mid;
                }
                else if (v[left] > v[right])
                {
                    return right;
                }
                else
                {
                    return left;
                }
            }
            return mid;
        }

        // 快排挖坑
        int _quickSort1(T &v, int left, int right)
        {
            // 使用三数取中进行优化
            int index = GetMidIndex(v, left, right);
            swap(v[index], v[left]);

            // 设置坑位
            int beign = left, end = right;
            int key = beign;
            int pivot = beign;

            while (beign < end)
            {
                // 开始找小
                while (v[end] >= key && beign < end)
                {
                    end--;
                }

                // 找到了,当前值放入原坑位，当前下标为新坑位
                v[pivot] = v[end];
                pivot = end;

                // 开始找大
                while (v[beign] <= key && beign < end)
                {
                    beign++;
                }

                v[pivot] = v[beign];
                pivot = beign;
            }

            // beign == end
            pivot = beign;
            v[pivot] = key;

            return pivot;
        }

        // 快排Horae
        int _quickSort2(T &v, int left, int right)
        {
            // 使用三数取中进行优化
            int index = GetMidIndex(v, left, right);
            swap(v[index], v[left]);

            // 设置标志位
            int beign = left, end = right;
            int key = beign;

            while (beign < end)
            {
                // 右边开始找小
                while (v[end] >= v[key] && beign < end)
                    end--;

                // 右边找到最小值，现在左边开始找大
                while (v[beign] <= v[key] && beign < end)
                    beign++;

                // 找到大于key与小于key的值，直接进行交换
                swap(v[beign], v[end]);
            }

            // beign == end
            swap(v[beign], v[key]);
            key = beign;

            return key;
        }

        // 快排前后指针
        int _quickSort3(T &v, int left, int right)
        {
            // 使用三数取中进行优化
            int index = GetMidIndex(v, left, right);
            swap(v[index], v[left]);

            int cur = left + 1;
            int prev = left;
            int key = prev;

            // cur用来找比key的值
            while (cur <= right)
            {
                if (v[cur] <= v[key])
                {
                    prev++;
                    swap(v[cur], v[prev]);
                }
                cur++;
            }

            // cur遍历完，prev下标位置就是key的固定下标
            swap(v[key], v[prev]);
            key = prev;

            return key;
        }

        // 向下调整算法
        void AdjustDwon(T &v, int n, int root) // n用于表示最大元素个数
        {
            int child = 2 * root + 1;

            while (child < n) // 检查孩子是否越界
            {
                if (child + 1 < n && v[child] < v[child + 1]) // 右孩子存在,值大于左孩子
                {
                    child++;
                }

                if (v[root] < v[child]) // 向下调整
                {
                    swap(v[root], v[child]);
                    root = child;
                    child = root * 2 + 1;
                }
                else
                {
                    // 不用再调整了
                    break;
                }
            }
        }

        // 归并递归
        void _MergeSort(T &v, T &temp, int left, int right)
        {
            if (left >= right)
                return;

            // 分开区间
            int mid = left + ((right - left) >> 1);

            _MergeSort(v, temp, left, mid);
            _MergeSort(v, temp, mid + 1, right);

            // 递归回来的时候相当于后续遍历
            // 划分子区间
            int beign1 = left, end1 = mid;
            int beign2 = mid + 1, end2 = right;
            int i = left; // 用于记录区间最开始的位置

            // 归并
            while (beign1 <= end1 && beign2 <= end2) // 其中一个数组结束直接跳出循环
            {
                if (v[beign1] < v[beign2]) // 判断两个子数组中元素的大小
                {
                    // 将较小的数放入到temp中
                    temp[i++] = v[beign1++];
                }
                else
                {
                    temp[i++] = v[beign2++];
                }
            }

            // 其中一个数组跑完了
            while (beign1 <= end1)
            {
                temp[i++] = v[beign1++];
            }

            while (beign2 <= end2)
            {
                temp[i++] = v[beign2++];
            }

            // 将排序好的数组拷贝回原数组中
            int n = right - left + 1;
            while (left <= right)
            {
                v[left] = temp[left];
                left++;
            }
        }
    };
}

int main()
{
    vector<int> v({9, 6, 2, 7, 5, 8, 3, 1, 4, 0});
    MySort::sort<vector<int>> *s = new MySort::sort<vector<int>>();

    // s->InsertSort(v);
    // s->ShellSort(v);
    // s->HeapSort(v);
    // s->BubbleSort(v);
    // s->SelectSort(v);
    // s->MergeSort(v);
    s->QuickSock(v);

    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;

    delete s;

    return 0;
}